class Solution
{
public:
    int mostBooked(int n, vector<vector<int>> &meetings)
    {
        return arrangeRoomsByHeap(n, meetings);
    }

    int arrangeRoomsByHeap(int n, vector<vector<int>> &meetings)
    {
        // pair<long long, int> 表示会议室下次可用时刻，会议室编号
        vector<pair<long long, int>> meetingRoomEndTime(n, pair<long long, int>(0LL, 0));

        for (int i = 0; i < n; ++i)
        {
            meetingRoomEndTime[i].second = i;
        }

        // 维护两个最早可用的会议室的堆，注意RoomEndTimeComparator的比较方法
        // 按结束时间由小到大排序，结束时间相同时按会议室序号由小到大排序
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, RoomEndTimeComparator> rooms1(meetingRoomEndTime.begin(), meetingRoomEndTime.end()), rooms2;

        vector<int> meetingRoomHeldCount(n, 0);

        // 无论是否延期，会议的举办顺序总是按start由小到大来的
        sort(meetings.begin(), meetings.end());

        for (auto &meeting : meetings)
        {
            auto room = rooms1.top();

            // 会议时间前闭后开，这里必须是<=
            if (room.first <= meeting[0])
            {
                // 可用时间 < 会议开始时间，即会议室空闲，则应该把所有空闲会议室都找出来
                // 然后编号最小的会议室的可用时间 = 会议结束时间
                while (!rooms1.empty())
                {
                    auto tempRoom = rooms1.top();
                    rooms1.pop();
                    if (tempRoom.first <= meeting[0])
                    {
                        tempRoom.first = 0;
                    }
                    rooms2.push(tempRoom);
                } // 借助两个堆来回倒，将所有空闲会议室置0
                rooms1.swap(rooms2);
                room = rooms1.top();
                rooms1.pop();
                room.first = meeting[1];
                rooms1.push(room);
            }
            else
            {
                // 会议室不空闲，则会议延期，再次可用时间是加上会议持续时间
                rooms1.pop();
                room.first += meeting[1] - meeting[0];
                rooms1.push(room);
            }

            meetingRoomHeldCount[room.second] += 1;
        }

        auto maxIt = max_element(meetingRoomHeldCount.begin(), meetingRoomHeldCount.end());
        return maxIt - meetingRoomHeldCount.begin();
    }

    class RoomEndTimeComparator
    {
    public:
        bool operator()(const pair<long long, int> &left, const pair<long long, int> &right)
        {
            if (left.first == right.first)
            {
                return left.second > right.second;
            }
            return left.first > right.first;
        }
    };
};